Приложения конструктивных описаний графов
При использовании конструктивного подхода для решения задач на
графах в качестве исходных выбираются максимальные по включению
графы, для которых рассматриваемая задача решается наиболее эффективно.
Далее из них строится суперпозиция, реализующая заданный граф. Анализ
структура графа упрощается, если строить его «по кирпичику», когда, по
крайней мере, один из графов-операндов каждой операции склейки
принадлежит множеству исходных графов, т.е. если пользоваться
каноническими суперпозициями. В качестве примера далее рассматриваются
задачи оптимального размещения информации (графов).
Решение широкого круга прикладных задач связано с размещением
объектов той или иной природы в элементах определенных структур.
Необходимость в подобных задачах возникает, например, при расположении
данных в памяти ЭВМ, расстановке оборудования в цехах, размещении
электронных схем на платах и т.д.
Размещаемые объекты обладают, как правило, определенной
совокупностью взаимосвязей, задаваемых соответствующим графом. Задача
состоит в поиске такого размещения вершин графа, при котором достигался
бы экстремум некоторого функционала, характеризующего свойства
размещения.
Решение задач размещения графов требует в общем случае проведения
перебора большого числа вариантов. Ограничимся здесь случаем линейного
размещения, когда вершины графов располагаются в заданных позициях
вдоль прямой. Выберем в качестве таковых целочисленные точки прямой.
При этом задачу можно сформулировать как задачу нумерации вершин графа
натуральными числами.
1.Свойства минимальных нумераций
Пусть G(V,E) граф, содержащий n вершин; A={a
1
, a
2
,..., a
n
}, a
i
< a
i+1
,
i=1,2,…,n-1 - множество из n натуральных чисел. Взаимнооднозначное
отображение
: V(G)
A называется нумерацией вершин графа G
(нумерацией графа), а множество A – нумерующей последовательностью
графа G. Рассматривается функционал
( , )
| ( ) ( )|,
ij
v v E
ij
G v v
(1.1)
где суммирование производится по всем ребрам графа G. Любая нумерация,
на которой достигается
min GG
, называется минимальной
нумерацией графа G. При решении задачи построения минимальной
нумерации достаточно ограничиться рассмотрением связных графов G,
поскольку в противном случае задача распадается на несколько
независимых подзадач. Из вида минимизируемого функционала (1.1)
следует, что, не ограничивая общности рассмотрения, можно полагать, что
нумерующая последовательность содержит n первых натуральных чисел,
т.е. A={1,2, . . ., n}. При этом
G
не больше, чем при выборе любой другой
нумерующей последовательности.
Рассмотрим далее класс деревьев. Для задачи построения минимальной
нумерации вершин деревьев в качестве исходных поддеревьев удобно взять
цепи
(V,E), для которых эта задача решается наиболее просто.
Лемма 1.1. Нумерация
цепи
(V,E) является минимальной тогда и
только тогда, когда
монотонна.
Доказательство. Рассмотрим линейную укладку графа
(V,E),
разместив вершины цепи
(V,E) вдоль числовой прямой таким образом,
чтобы каждая вершина
i
vV
попала в точку с координатой
()
i
v
. При этом
каждому ребру
( , )
ij
v v E
будет соответствовать отрезок [
()v
i
,
()
j
v
]. Из
вида функционала (1.1) следует, что
( , )VE
равно сумме длин всех таких
отрезков. Поскольку наибольшее и наименьшее значения номеров вершин
фиксированы, то указанная сумма будет минимальной тогда и только тогда,
когда отрезки [
()v
i
,
()
j
v
], соответствующие различным ребрам, не
пересекаются, т.е. когда нумерация монотонна.
Каждое дерево можно, очевидно, рассматривать как результат
объединения пореберно непересекающихся цепей. Для произвольной
нумерации
структуру дерева t можно представить следующим образом
(рис. 1.1). Поддеревья
1,( , ),
i i i
kV E it
порождены ребрами, не
принадлежащими цепи
(V
0
,E
0
), соединяющей вершины
1
(1)
и
1
()n
.
1
(1)
(V
0
,E
0
)
1
()n
1
t
2
t
. . .
1k
t
k
t
Рисунок 1.1
Лемма 1.2. Если
минимальная нумерация дерева t{V,E), то:
1) нумерация цепи
(V
0
,E
0
) монотонна,
2) нумерующие последовательности поддеревьев
1,( , ),
i i i
kV E it
сплошные.
Доказательство. Поскольку множества ребер цепи
(V
0
,E
0
) и
поддеревьев
1,( , ),
i i i
kV E it
попарно не пересекаются, то
00
1
( , ) ( , ) ( , )
k
i i i
i
V E V E V Ett
. (1.2)
Предположим, что минимальная нумерация
не удовлетворяет
условиям леммы, т.е. нумерация цепи
(V
0
,E
0
) не монотонна и (или)
найдется хотя бы одно поддерево
1,( , ),
i i i
kV E it
, нумерующая
последовательность которого не является сплошной. Построим по
нумерацию
, удовлетворяющую условиям леммы, что всегда возможно при
сплошной нумерующей последовательности всего дерева, и обладающую
следующими свойствами.
Вершины
1
(1)
и
1
()n
совпадают соответственно с вершинами
1
(1)
и
1
()n
, порядок нумерации внутри каждого поддерева
1,( , ),
i i i
kV E it
сохраняется неизменным. Аналогично (1.2), можно записать
00
1
( , ) ( , ) ( , )
k
i i i
i
V E V E V Ett
. (1.3)
Учитывая лемму 1.1, для нумераций
и
на цепи
(V
0
,E
0
)
справедливо соотношение
0 0 0 0
( , ) ( , )V E V E
. (1.4)
Из вида оптимизируемого функционала (1.1) и способа построения
нумерации
по нумерации
следует что
( , ) ( , ), 1,
i i i i i i
V E V E i ktt
(1.5)
Из предположения о нумерации
следует, что в (1.4) и (или) в (1.5)
(хотя бы для одного поддерева) имеет место строгое неравенство.
Отсюда,
сопоставляя (1.3) и (1.2), получаем
( , ) ( , )V E V Ett
,
что противоречит условию минимальности нумерации
.
Следствие 1.1. Минимальная нумерация
дерева t(V,E) является
минимальной и на каждом его поддереве
1,( , ),
i i i
kV E it
, т.е.
( , ) ( , ), 1,
i i i i i i
V E V E i ktt
. (1.6)
Любой нумерации
графа G,
| ( ) |VG n
можно сопоставить
двойственную нумерацию
такую, что
( ) 1 ( ), 1,
ii
v n v i n
. Очевидно,
что
GG
. Вершины графа степени один будем называть для краткости
висячими.
Лемма 1.3. Если
минимальная нумерация дерева t(V,E), то вершины
1
(1)
и
1
()n
являются висячими.
Доказательство. Ограничимся рассмотрением вершины
1
(1)
,
учитывал возможность перехода к двойственной нумерации
.
Предположим, что вершина
1
(1)
не является висячей. Выделим в
t{V,E) цепь
(V
0
,E
0
), соединяющую вершины
1
(1)
и
1
()n
, а также
поддеревья
1,( , ),
i i i
kV E it
. Вершине
1
(1)
соответствует поддерево
1 1 1 1 1 1
,2( , ),| |V E V n nt
. Из леммы 1.2 следует, что его нумерующая
последовательность состоит из чисел 1,2,…,
1
n
. Построим нумерацию
1
,
совпадающую с нумерацией
на всех вершинах
1
i
vV
, а на вершинах
1
i
vV
совпадающую с двойственной нумерацией:
1
1
( ) 1 ( ), 1,
ii
v n v i n
. При
переходе к нумерации
1
монотонность нумерации цепи
(V
0
,E
0
), очевидно,
сохранится. Поскольку
1
11
( (1)) 2n
, то
0 0 0 0
1
1
)( , 1 ( , )V E n n n V E
. Так как
1
( , ) ( , ), 1,
i i i i i i
V E V E i ktt
, то, сравнивая разложения (1.2) для
нумераций
и
1
, получаем
1
( , ) ( , )V E V Ett
, что противоречит
условию минимальности нумерации
.
Из лемм 1.2 и 1.3, учитывая равенства (1.6), получаем
Следствие 1.2. Если
минимальная нумерация дерева t(V,E), то его
можно разложить на последовательность пореберно непересекающихся
цепей
j
(V
j
,E
j
),
1,jl
таких, что:
1) концевые вершины цепей являются висячими в тех поддеревьях, в
которых они выделяются;
2) нумерация каждой цепи монотонна, а нумерующие
последовательности всех поддеревьев, образующихся в процессе
разложения, сплошные.
Все нумерации, в которых можно выделить указанную
последовательность цепей, образуют класс нумераций
*
.
Таким образом, для реализации минимальных нумераций необходимо
строить дерево t(V,E) из цепей
j
(V
j
,E
j
),
1,jl
путем склейки графов-
операндов по O
1
, причем чтобы отождествляемая вершина хотя бы в одном
из графов-операндов имела четную степень (операции
1
H
- склейки). Пусть
множество всех простых цепей, тогда для построения минимальной
нумерации каждое дерево представляется в виде
1
H
- суперпозиции над
.
Из леммы 4.1.1 следует, что при этом допустима и каноническая
1
H
-
суперпозиция над
.
2.Минимальные плоские размещения
Рассмотрим свойства нумераций
*
, соответствующих реализациям
дерева t(V,E) каноническими
1
H
- суперпозициями над
. Линейная
укладка дерева t(V,E) называется плоской, если она допускает
геометрическую реализацию графа в полуплоскости. Соответствующая
ей нумерация также называется плоской. Нумерация
является
плоской тогда и только тогда, когда между номерами вершин
произвольной пары ребер (v,v
j
) и (v
k
,v
r
) не существует соотношений:
(v
i
) <
(v
k
) <
(v
j
) <
(v
r
) или
(v
k
) <
(v
i
) <
(v
r
) <
(v
j
). (2.1.)
Не ограничивая общности рассмотрения, полагаем в (2.1)
(v
i
) <
(v
j
),
a
(v
k
) <
(v
r
).
Класс плоских нумераций пересекается с классом нумераций
Ф*(например, монотонная нумерация любой цепи
(V,E)), однако ни
один из них не содержится целиком в другом (рис. 2.1.).
плоская
*
неплоская
*
Рисунок 2.1.
Теорема 2.1. Нумерация
*
вершин дерева t(V,E) является плоской
тогда и только тогда, когда соответствующая ей
2
3
1
1
2
2
1
3
4
5
6
1
2
3
4
5
6
3
последовательность цепей разложения
j
(V
j
,E
j
),
1,jl
обладает
следующим свойством
1
k
j
j
связно при
2, 1kl
(2.2)
Доказательство. Необходимость. Покажем, что если нумерация
*
является плоской, то условие (2.1) выполнено. Предположим, что
найдется хотя бы одно
2, 1kl
такое, что
1
1
k
j
j
не имеет общей вершины с
цепью
k
. Выделим в дереве цепь, соединяющую вершину
k
j
v
цепи
k
с
вершиной
q
i
v
из
1
1
k
j
j
, не содержащую ребер из
k
и
1
1
k
j
j
. Пусть
q
1
1
k
j
j
цепь (одна из цепей), содержащая вершину
q
i
v
.
Так как
*
, то вершины
q
i
v
и
k
j
v
не могут быть концевыми в
указанных цепях, поскольку они не являются висячими в поддеревьях, в
которых выделяются цепи
q
и
k
. Обозначим через
1
q
i
v
и
1
q
i
v
(
1
k
j
v
и
1
k
j
v
)
вершины, смежные с
q
i
v
(
k
j
v
) на цепи
q
(
k
). Поскольку нумерация вдоль
каждой цепи разложения монотонна, то, не ограничивая общности,
можно положить
(
1
q
i
v
) <
(
q
i
v
) <
(
1
q
i
v
) и
(
1
k
j
v
) <
(
k
j
v
) <
(
1
k
j
v
).
(2.3)
Отсюда, учитывая порядок выделения цепей и сплошность
нумерующих последовательностей всех поддеревьев разложения, получаем
соотношения
(
1
q
i
v
) <
(
1
k
j
v
) <
(
q
i
v
) и
(
q
i
v
) <
(
1
k
j
v
) <
(
1
q
i
v
) (2.4)
Из (2.3) и (2.4) следует, что при любом соотношении между номерами
(
q
i
v
) и
(
k
j
v
) среди ребер множества {(
1
q
i
v
,
q
i
v
),(
q
i
v
,
1
q
i
v
),(
1
k
j
v
,
k
j
v
),(
k
j
v
,
1
k
j
v
)}
всегда найдутся такие два ребра, для которых будет справедливо одно из
неравенств (2.1), т.е. нумерация
не будет плоской.
Достаточность. Пусть нумерация
*
вершин дерева t(V,E)
удовлетворяет условию теоремы. Разместим вершины
, 1,
i
v V i n
вдоль
целочисленной прямой в точках с координатами
(
i
v
) и соединим дугами
смежные вершины. Дуги, соответствующие ребрам одной цепи,
очевидно, не пересекаются, так как нумерация вдоль каждой цепи
j
,
1,jl
монотонна. Покажем, что не могут пересекаться и дуги,
соответствующие различным цепям. Действительно, из сплошности
нумерующих последовательностей всех поддеревьев разложения
следует, что внутри отрезка, заключенного между номерами концевых
вершин любой цепи
j
,
2,jl
содержится номер лишь одной вершины
i
v
,
входящей в цепи множества {
1
, . . . ,
j-1
}. Учитывал связность
1
j
r
r
,
вершина
i
v
обязательно принадлежит и цепи
j
, т.е. дуги цепи
j
не
пересекаются с дугами цепей из множества {
1
, . . . ,
j-1
}. Рассматривая
последовательно дуги цепей
j
,
2,jl
, убеждаемся в справедливости
утверждения о том, что
плоская нумерация.
Условие (2.2) означает, что все нумерации
*
,
соответствующие каноническим
1
H
- суперпозициям над
, являются
плоскими.
Лемма 2.1. Всякая минимальная плоская нумерация
дерева t(V,E)
принадлежит классу
*
.
Доказательство. Разложим дерево t(V,E) на пореберно
непересекающиеся цепи
j
(V
j
,E
j
),
1,jq
, соединяющие в каждом поддереве
разложения вершины с наименьшими и наибольшими номерами.
Покажем, что если
минимальная плоская нумерация, то указанное
разложение обладает всеми свойствами нумераций из класса Ф* и,
следовательно q =l.
Если нумерующая последовательность хотя бы одного поддерева
разложения, образующегося в процессе выделения цепей
j
(V
j
,E
j
) не
является сплошной, то нумерация
не будет плоской, поскольку
нумерующая последовательность всего дерева сплошная и каждое
поддерево разложения связно.
Если хотя бы одна из концевых вершин некоторой цепи
j
(V
j
,E
j
),
1,jl
не является висячей в поддерева, в котором она выделяется, то, не
выходя из класса плоских нумераций, можно уменьшить значение
функционала (1.1), перейдя к двойственной нумерации на поддереве,
"висящем" на такой концевой вершине.
Если хотя бы на одной из цепей
j
(V
j
,E
j
),
1,jl
нарушена
монотонность, то нумерация
не будет плоской, поскольку концевые
вершины всех цепей
j
(V
j
,E
j
),
1,jl
являются висячими и имеют
наименьший и наибольший номера в поддереве, в котором эта цепь
выделяется.
Рассмотрим, какие канонические
1
H
- суперпозиции над
соответствуют минимальным плоским нумерациям. Выделим в дереве t{V,E)
произвольную вершину
i
vV
степени s(v
i
)=p и все инцидентные ей ребра
(v
i
,v
r
),
1,rp
. Любая вершина v
q
v
i
связана с вершиной v
i
единственной
цепью. Будем говорить, что вершина v
q
принадлежит ветке, выходящей из
вершины v
i
по ребру (v
i
,v
r
),
1,rp
, если в v
q
можно попасть из v
i
по цепи,
содержащей ребро (v
i
,v
r
). Число вершин ветки определяет её вес.
Теорема 2.2. Плоская нумерация
*
произвольного дерева t(V,E)
является минимальной тогда и только тогда, когда цепи
j
(V
j
,E
j
),
1,jl
проходят через вершины дерева по веткам наибольшего веса.
Доказательство. Необходимость. Пусть
минимальная плоская
нумерация дерева t(V,E). Для вершин
i
vV
степени s(v
i
)
2 необходимость
условия теоремы очевидна. Рассмотрим произвольную вершину
i
vV
степени s(v
i
)
3. Выделим два случая.
1.Цепь
1
проходит через вершину v
i
. При этом из теоремы 1.1, леммы
1.4 и свойств нумераций класса
*
следует, что нумерующие
последовательности всех веток к v
i
будут сплошными. Взаиморасположения
их вдоль числовой прямой приведены на рис.2.2.
1
(
1
i
v
)
(
1p
i
v
)
(v
i
)
(
p
i
v
)
(
2
i
v
)
n
1
n
1p
n
1p
n
2
n
p - четно
1
(
1
i
v
)
(
2p
i
v
)
(v
i
)
(
1p
i
v
)
(
2
i
v
)
n
1
n
n
p-2
n
p
1p
n
n
2
p – нечетно.
Рисунок 2.2.
Поскольку минимальная плоская нумерация
дерева t(V,E)
принадлежит классу
*
, то
21k
n
и
2k
n
,
1, / 2kp
- число вершин в ветках,
по которым k-ая цепь разложения проходит через вершину v
i
. При
нечетном p указаны две возможности для нумерации вершины v
i
, поскольку
последняя цепь разложения проходит через v
i
только по одной ветке (с
числом вершин п
р
) и в зависимости от выбора направления нумерации
на этой цепи последняя ветка может быть занумерована как до, так и
после вершины v
i
(в последующих расчетах выбран вариант, когда
последняя ветка занумерована до вершины v
i
).
Из сплошности нумерующих последовательностей всех веток к v
i
следует возможность перехода на каждой из них к двойственной нумерации.
При этом сумму длин всех ребер, инцидентных вершине v
i
величину
1
| ( ) ( )|
p
ij
j
vv
, можно оценить сверху следующим образом:
/2 /2 /2
1 1 1
2 1 2 2 1 2
2 2 2
1
2 1 1
( 1)( ) ( ) ( )
p p p p
i
k k k k
i
k k k
k n n n k n k n
(2.4)
при p четном
/2 /2 /2 /2
11
2 1 2 1 2 2
22
2 1 2 1
{{( 1) } ( 1) }
p p p p
k k k k
k k k k
k n n k n n
/2 /2
11
2 1 2
22
11
( ) ( )
pp
kk
kk
k n k n
(2.5)
при p нечетном.
Необходимым условием минимальности каждого из выражений (2.4) и
(2.5) является, очевидно, выполнение для первой взвешенной суммы
соотношений
21
21
, , 1, / 2 , 2, / 2
r
k
n n r k r p k p
, а для второй
взвешенной суммы соотношений
2
2
, , 1, / 2 , 2, / 2
r
k
n n r k r p k p
. В
противном случае, поменяв порядок нумерации вершин соответствующих
веток, можно уменьшить величину
1
| ( ) ( )|
p
ij
j
vv
, что противоречит
минимальности нумерации
. Таким образом, для всех вершин v
i
, через
которые проходит цепь
1
, условия теоремы выполнены, то есть все цепи
разложения
j
(V
j
,E
j
),
1,jl
проходят через вершины v
i
по веткам с
наибольшим числом вершин.
2.Цепь
1
не содержит вершину v
i
. Пусть
, 2, 1
k
kl
- первая цепь
разложения, проходящая через v
i
. Так как
1
k
j
j
связно при
2, 1kl
, то
цепь
k
обязательно проходит через v
i
по ветке, содержащей предыдущие
выделенные цепи
, 1, 1
j
jk
. Число вершин в этой ветке больше, чем в
какой-либо другой ветке к v
i
, так как она содержит цепь
1
, проходящую
через вершины дерева по веткам с наибольшим числом вершин.
Следовательно, нарушение условий теоремы невозможно ни на какой
паре веток к v
i
, одна из которых содержит цепь
1
. Поскольку нумерация
остальных веток к v
i
производится сплошными нумерующими
последовательностями, то дальнейшее доказательство проводится
аналогично первому случаю. Итак, и для всех вершин v
i
, через которые не
проходит цепь
1
, условия теоремы также выполнены, то есть все цепи
разложения
j
(V
j
,E
j
),
1,jl
проходят через такие вершины v
i
по веткам с
наибольшим числом вершин.
Достаточность. Нетрудно видеть, что если способ выделения
цепей
j
(V
j
,E
j
),
1,jl
удовлетворяет условиям теоремы, то
1
k
j
j
,
2, 1kl
связно. По теореме 2.1 любая нумерация
*
является при этом
плоской. Все такие нумерации обладают, кроме того, одинаковым
значением минимизируемого функционала (1.1). Действительно, если
нумерации отличаются лишь направлением роста номеров вдоль
некоторых цепей
j
(V
j
,E
j
),
1,jl
, то справедливость доказываемого
утверждения непосредственно следует из свойств нумераций класса Ф* и
вида минимизируемого функционала (1.1).
Если меняется разложение на цепи
j
(V
j
,E
j
),
1,jl
, то это влияет лишь
на порядок нумерации веток с одинаковым числом вершин для
некоторых
i
vV
. Из способа выделения цепей следует, что ветки к любой
вершине v
i
, содержащие одинаковое число вершин, имеют сплошные
нумерующие последовательности. Поэтому, меняя порядок их
нумерации, всегда можно перейти от одного разложения к другому,
сохранив неизменным значение функционала (1.1).
Поскольку минимальные плоские нумерации содержатся среди
рассматриваемых (это следует из необходимости условий теоремы),
получаем отсюда минимальность всех нумераций, удовлетворяющих
условиям теоремы.
Алгоритм построения минимальной плоской нумерации
На основе теоремы 1.2 можно предложить алгоритм построения
минимальной плоской нумерации вершин произвольного дерева.
Основу его составляет следующая процедура:
1. Выбрать в текущем поддереве разложения (исходном дереве)
произвольную вершину дерева v
0
.
2. Перейти от вершины v
0
по веткам с наибольшим числом вершин в
некоторую висячую вершину v
1
.
3. Начиная от вершины v
1
, построить по веткам с наибольшим числом
вершин цепь в некоторую другую висячую вершину v
2
.
4. Присвоить вершинам v
1
и
v
2
наибольшие и наименьшие номера из
диапазона, выделенного под текущее поддерево разложения (1 и n для
исходного дерева).
5. Занумеровать монотонно цепь, соединяющую вершины v
1
и
v
2
,
оставляя под каждое выделяемое поддерево разложения соответствующие
диапазоны номеров.
Процедура повторяется до тех пор, пока не будут занумерованы все
вершины.
ПРИМЕР 2.1. Для нижеприведенного дерева одна из возможных
минимальных плоских нумераций имеет следующий вид:
1
2
3
4
5
8
6
7
7
Для реализации алгоритма необходимо предварительно вычислить веса
веток ко всем вершинам дерева и упорядочить их. Для произвольного n –
вершинного дерева это можно сделать с линейной трудоемкостью O(n),
используя дополнительную память объема O(n log n) [12].
Для небольших деревьев с n
15 минимум функционала (1.1) в классе
плоских нумераций совпадает с глобальным минимумом в классе всех
нумераций. Для больших значений n минимум в классе плоских нумераций в
общем случае не позволяет достичь глобального минимума, достигаемого на
нумерациях, которым соответствуют реализации деревьев
1
H
-
суперпозициями над , не являющимися каноническими.
ПРИМЕР 2.2. Для следующего дерева t(V,E) с числом вершин n=16
минимальная нумерация не является плоской.
минимальная плоская нумерация
минимальная нумерация
( , )VEt
26
( , )VEt
25
3.Оценки длин деревьев
Алгоритм построения минимальной нумерации произвольного
дерева имеет сложную рекурсивную структуру с трудоемкостью
2
log 3
()On
[13]. Относительно простой алгоритм построения
минимальной плоской нумерации можно рассматривать как способ
1
2
3
4
5
7
8
9
6
10
11
12
15
16
13
14
1
2
5
3
4
8
7
6
9
10
11
13
14
12
15
16
приближенного решения задачи построения минимальной нумерации.
В работе [12] показано, что минимум в классе плоских нумераций
может превосходить глобальный минимум не более чем в полтора раза.
Каково значение самого минимума, насколько оно отличается,
например, от среднего значения функционала (1.1) на множестве всех
n! нумераций. Оценим минимум сверху через максимальное значение
функционала (1.1) на множестве всех n – вершинных деревьев при
использовании нумераций
*
.
Геометрическая интерпретация нумераций класса
*
Рассмотрим линейную укладку дерева t(V,E),|V|=n соответствующую
произвольной нумерации
*
. Для этого разместим вершины дерева вдоль
числовой прямой таким образом, чтобы каждая вершина
i
vV
попала в
точку с координатой
()v
i
. Выделим вершины, являющиеся концевыми для
цепей разложения
j
(V
j
,E
j
),
1,jl
, и соединим их дугами. Для цепи
j
(V
j
,E
j
),
1,jl
номера концевых вершин обозначим через
j
a
и
j
a
. Каждой цепи
j
(V
j
,E
j
),
1,jl
будет соответствовать отрезок [
j
a
,
j
a
],
1,jl
. Так как
*
,
то отрезки различных цепей не пересекаются и не имеют общих точек (рис.
3.1).
. . . . . . . . .
1
j
a
j
a
n
Рисунок 3.1
Разобьем множество всех дуг на ярусы. К первому ярусу отнесем
внешнюю дугу, соединяющую, очевидно, точки с координатами 1 и n и
соответствующую цепи
1
(V
1
,E
1
). Ко второму ярусу отнесем дуги, которые
становятся внешними после удаления дуги первого яруса. Они соответствуют
цепям, выделяемым в поддеревьях, образующихся после выделения цепи
1
(V
1
,E
1
) и т.д.
Обозначим через q - общее число ярусов, n
i
-число цепей i -го яруса,
, 1, , 1,
i
ik
i q k n
- цепь, соответствующая k -ой дуге i -го яруса.
Теорема 3.1. Для любого дерева t(V,E),|V|=n и нумерации
*
t
n
2
/4
Доказательство. Поскольку цепи
j
(V
j
,E
j
),
1,jl
пореберно не
пересекаются, то можно записать рассматриваемый функционал
t
так
1
1
i
n
q
ik
i
k
t
. (3.1)
Так как нумерация
на каждой цепи
ik
монотонна, то величина
ik
равна длине отрезка [
ik
a
,
ik
a
]. Отрезки, соответствующие цепям
одного яруса, очевидно, не имеют общих точек. Тогда, учитывал способ
разбиения цепей на ярусы, получаем
1
1
1
( 1) 2 ( 1)
n
i
i
r
i
ik
r
k
n l n
. (3.2)
Учитывая, что n
i
1,
1,iq
, q
n/2, из (3.1) и (3.2) следует
/2
1
( 2 1)
n
i
t n i
nn/2 - n/2 n/2 + n/2 = n/2 n/2 = n
2
/4
при n нечетном,
/2
1
( 2 1)
n
i
t n i
n(n/2)- (n/2) (n/2+1) + n/2= n/2(n/2-1)+ n/2=n
2
/4
при n четном.
Таким образом, утверждение теоремы справедливо при любом n.
Подсчитаем среднее значение минимизируемого функционала (1.1) для
произвольного графа G(V,E), /V/=n на множестве всех n! нумераций
величинуравную
!
1
( )/ !
n
i
i
Gn
(3.3)
При последовательном построении n! нумераций на концах любого
ребра e
E каждая пара номеров
, ; ; , 1,i j i j i j n
побывает 2(n-2)! раз.
Длина ребра e принимает при этом значения |i- j| равные
1, 1kn
по (n-k)
раз. Общий вклад ребра e в числитель выражения (3.3) равен
1
1
( 1) (2 1)( 1) ( 1)!
2( 2)! ( ) 2( 2)!( )
2 3 3
n
k
n n n n n n
n k n k n n
.
Поскольку это верно для произвольного ребра e
E , то числитель в
(3.3) равен
( 1)!/3En
и среднее значение длины графа G на множестве всех
n! нумераций равно
( 1)/3En
.
Так как в дереве t(V,E),|V|=n число ребер |E|= n-1, то среднее значение
длины дерева на множестве всех нумераций равно (n
2
-1)/3. Учитывая
утверждение теоремы 3.1, получаем, что при
n
значение
минимизируемого функционала 1.1 на множестве нумераций из класса
*
, по
крайней мере, на четверть меньше среднего значения на множестве всех
нумераций. При использовании минимальных нумераций или минимальных
плоских нумераций сокращение длины дерева может быть еще значительнее.
